package com.ling.algorithm;

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.HashSet;

/**
 * guide 字符串常见题目
 */
public class StringSolution {



//    public static void main(String[] args) {
//        String weAreHappy = replaceSpace("We Are Happy");
//        System.out.println(weAreHappy);
//    }

    /**
     * 剑指 offer：请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为 We Are Happy.则经过替换之后的字符串为 We%20Are%20Happy。
     */
    public static String replaceSpace(String str){
        String replace = str.replaceAll("\\s", "%20");
        return replace;
    }

//    public static void main(String[] args) {
//        String[] strs = { "flower","flow","flight" };
//        String s = replaceSpace(strs);
//        System.out.println(s);
//    }

    /**
     * Leetcode: 编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 ""。
     */
    public static String replaceSpace(String[] strs){
        //检查字符串数组是否合法
        if (!checkStr(strs)){
            return "";
        }

        int length = strs.length;   //数组的长度

        StringBuilder stringBuilder = new StringBuilder();  //保存结果
        Arrays.sort(strs);      //最数组进行排序，然后取第一个和最后一个进行比较即可

        int x = strs[0].length();
        int m = strs[length - 1].length();
        int min = Math.min(x, m);
        for (int i = 0; i < min; i++) {
            if (strs[0].charAt(i) == strs[length - 1].charAt(i)){
                stringBuilder.append(strs[0].charAt(i));
            }else {
                break;
            }
        }
        return stringBuilder.toString();

    }

    public static Boolean checkStr(String[] strs){
        Boolean b = false;
        if (strs != null){
            for (int i = 0; i < strs.length; i++) {
                if (strs[i] != null && strs[i].length()>0){
                    b = true;
                }else {
                    b = false;
                    break;
                }
            }
        }
        return b;
    }

    /**
     * 统计最长回符串的长度
     */

    public static int longestPalindrome(String s){
        if (s.length() == 0){
            return 0;
        }
        /**
         * 利用hashset来判断字符是否存在，存在则count++
         */
        HashSet<Character> hashSet = new HashSet<>();
        int count = 0;

        for (int i = 0; i < s.length(); i++) {
            if (!hashSet.contains(s.charAt(i))){
                hashSet.add(s.charAt(i));
            }else {
                hashSet.remove(s.charAt(i));
                count ++;
            }
        }
        return hashSet.isEmpty()?count *2:count *2+1;
    }

//    public static void main(String[] args) {
//        int a = longestPalindrome("abccccdd");
//        System.out.println(a);
//    }

    /**
     * 验证回文串
     */

//    public static void main(String[] args) {
//        boolean b = islPalindrome("A man, a plan, a canal: Panama");
//        System.out.println(b);
//    }

    public static boolean islPalindrome(String str){
        if (str.length()==0){
            return false;
        }
        int max = str.length()-1;
        int min = 0;
        while (min<max){
            if (!Character.isLetterOrDigit(str.charAt(min))){
                min++;
            } else if (!Character.isLetterOrDigit(str.charAt(max))) {
                max--;
            }else {
                if (Character.toLowerCase(str.charAt(max)) != Character.toLowerCase(str.charAt(min))){
                    return false;
                }
                max--;
                min++;
            }
        }
        return true;
    }

    /**
     * Leetcode: LeetCode: 最长回文子串 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
     * 以某个元素为中心，分别计算偶数长度的回文最大长度和奇数长度的回文最大长度。
     */

    public static void main(String[] args) {
        String babad = maxLongestPalindrome("babfdbsgadrad");
        System.out.println(babad);
    }

    private static int index, len;
    public static String maxLongestPalindrome(String s){
        if (s.length()<2){
            return s;
        }
        for (int i = 0; i < s.length() -1; i++) {
            palindromeHelper(s,i,i);
            palindromeHelper(s,i,i+1);
        }

        return s.substring(index,index+len);
    }

    public static void palindromeHelper(String s,int i,int l){
        while (i>0 && l<s.length() && s.charAt(i) == s.charAt(l)){
            i--;
            l++;
        }

        if (len<l-i-1){
            index = i+1;
            len = l-i-1;
        }
    }
}
